Date: Tue, 26 Nov 1996 18:46:55 GMT
Server: NCSA/1.5.2
Last-modified: Tue, 26 Nov 1996 15:22:16 GMT
Content-type: text/html
Content-length: 4982

<!DOCTYPE HTML SYSTEM "html.dtd">
<HTML><HEAD><TITLE>CSC/ECE 505 title page</TITLE></HEAD>
<BODY><H1><!WA0><IMG SRC="http://www.ncsu.edu/images/ncsubell.gif" ALIGN="BOTTOM">
<p>CSC(ECE) 505: Design and Analysis of Algorithms</H1>
<!WA1><A HREF="http://www.csc.ncsu.edu/departmental/courses/CSC505.html">Official
course description from NCSU <em> Graduate
Catalog</em></A>
<P>


Instructor: Rex A. Dwyer, Associate Professor, Computer Science
<ul>
<li>E-mail: dwyer@csc.ncsu.edu
<li>Phone: (919) 515-7028
<li>Office: Withers Hall 226
<li>Office Hours: TBA
</ul>

<p>Teaching Assistant: TBA

<p>Meeting Time and Place:  Tues/Thurs 11:20-12:35, Withers Hall 210-A

<p>Prerequisites:  Data structures (CSC 311). Discrete Math (CSC 222) is
strongly recommended.

<p>Official WWW page: http://www.csc.ncsu.edu/eos/info/csc505_info/www/index.html
<p>Class broadcast e-mail list: csc505-001@csc.ncsu.edu
<p>Address for anonymous comments: csc505-001-comments@csc.ncsu.edu

<p>Textbook: Cormen, Leiserson, and Rivest, <i>Introduction to Computer Algorithms</i>, McGraw-Hill, 1990.
Errata for the textbook, instructor's notes for selected topics, and other
materials are on 
reserve in D.H. Hill Library and/or accessible from the class
WWW page.

<p>Grading:
<ul>
<li>Plus/minus grading will be used.
<li>30\% closed-book exam, Tues. Sept. 24.
<li>30\% closed-book exam, Thurs. Oct. 31. 
<li>40\% open-book final exam, Tues. Dec. 10, 8:00-11:00.
<li>0\% problem sets -- approximately every 10 days.
<li>No programming projects.
<li>Opportunities to earn extra credit are unlikely, and,
if available, will be offered to all students on the same basis.
</ul>

<p>Drop Date: October 25.  All changes in course status must be 
handled through the registrar.



<p>Problem Sets:

Homework problem sets will be assigned on a regular basis.  The problems are
generally pencil-and-paper problems, although it is not inappropriate to apply
computing resources.  Model solutions will be made available on specified due
dates.  The principal incentive for doing homework (aside from intellectual
curiosity!) is to be prepared for exams; no explicit credit will be given for
homework.  (If available TA resources permit, some problem sets will be
collected and selected problems will be read and commented upon.)  Since no
grades are assigned, you are free to work together; however, it is
important at exam time that you be able to write up solutions in your own
words.  One approach might be to meet with other students to discuss and
perhaps solve problems, then reconstruct the solution later without using
notes.

<p><b>Approximate Schedule:</b>
<ul>
<li> 8/22 Introduction;  Sec. 1
<li> 8/27 Asymptotics, Summations;  Sec. 2, Sec. 3
<li> 8/29 Divide and Conquer, Recurrences;  Sec. 31.2, Sec. 4; 
<!WA2><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln1.ps">HW1 due</a>
<li> 9/3 Quicksort;   Sec. 8
<li> 9/5 Order Statistics;  Sec. 10 
<li> 9/10 Heapsort, Lower Bounds;   Sec. 7, Sec. 9.1;
<!WA3><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln2.ps">HW2 due</a>
<li> 9/12 Linear-time Sorts;  Sec. 9.2-4
<li> 9/17 Leftist and Skew Heaps;   
<!WA4><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/skewheaps.ps">notes</a>
 & Sec. 18.1-3
<li> 9/19 Review; 
<!WA5><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln3.ps">HW3 due</a>
<li> <b>9/24 Exam 1</b>
<!WA6><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/exam1.ps"><i>
Last year's exam</i></a>

<li> 9/26 Binomial & Fibonacci Heaps;   Sec. 20, Sec. 21  
<li> 10/1  Disjoint Sets;  Sec. 22
<li> 10/3  Graphs;   Sec. 23.1;   
<!WA7><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln4.ps">HW4 due</a>
<li> 10/8 Depth- and Breadth-First Search;   Sec. 23.2-3  
<li> 10/10 Applications of Depth-First Search;   Sec. 23.4-5
<li> 10/17 Minimum Spanning Trees;   Sec. 24;
<li> 10/22 Single-Source Shortest Paths;   Sec. 25
<li> 10/24 Greedy Algorithms;   Sec. 17
<li> 10/29 Review;  
<!WA8><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln56.ps">HW5,HW6 due;</a>
<li> <b>10/31 Exam 2</b>
<!WA9><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/exam2.ps"><i>
Last year's exam</i></a>
<li> 11/5 P and NP;  Sec. 36.1-2  
<li> 11/7 NP-completeness;  Sec. 36.3-5
<li> 11/12 NP-completeness;    
<li> 11/14 Approximation Algorithms;  Sec. 37;
<!WA10><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/soln7.ps">HW7 due</a>
<li> 11/19 Dynamic Programming;   Sec. 16.1-3
<li> 11/21 All-Pairs Shortest Paths;   Sec. 26
<li> 11/26 Fast Fourier Transform;  Sec. 32
<li> 12/3 Computational Geometry;  Sec. 35;
<!WA11><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/prob8">HW8 due</a>
<li> 12/5 Review;
<!WA12><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/prob9">HW9 due</a>
<li> <b>12/10 Final Exam, 8:00-11:00</b>
<!WA13><A HREF="http://www.csc.ncsu.edu/eos/info/csc505_info/www/final.ps"><i>
Last year's final (closed-book)</i></a>
</ul>



<HR>
<HR></BODY>
<ADDRESS>dwyer@csc.ncsu.edu Rex Dwyer<BR>updated 8/20/96</ADDRESS></HTML>

